package com.cyy.test_t_4_;

import java.util.ArrayList;

/**
 * 剑指Offer 面试题41_2
 * 和为S的连续正数序列；
 * 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，
 * 序列间按照开始数字从小到大的顺序
 */
public class t_41_2 {

	public static void main(String[] args) {
		System.out.println(FindContinuousSequence(100));
	}
	
	
	public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
		
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		
		if(sum < 3) return result;
		
		int begin = 1;
		int end = 2;
		int middle = (1 + sum) / 2;
		
		while(begin != middle){
			
			int cur=SumOfList(begin,end);
			
			if(cur == sum){
				ArrayList<Integer> list = new ArrayList<Integer>();
				for(int i = begin; i <= end; ++ i){
					list.add(i);
				}
				result.add(list);
				begin ++;
				end ++;
			}else if(cur < sum){
				end ++;
			}else{
				begin ++;
			}
		}
		
	    return result;
    }
	
	public static int SumOfList(int start,int end){        //计算当前序列的和
        int sum=start;
        for(int i=start+1;i<=end;i++){
            sum+=i;
        }
        return sum;
    }
}
